The following relates to the pattern matching arts, graph matching arts, information comparison and retrieval arts, image comparison and retrieval arts, object comparison and retrieval arts, and related arts.
Objects such as two- and three-dimensional images, proteins, and so forth can be represented as geometrical objects in space, in which the representation is in the form of a graph embedded in a Euclidean space. Such a graph includes: (i) nodes, which can be thought of as points in the Euclidean space; and (ii) edges, which can be thought of as edges connecting pairs of nodes. A node optionally may have attributes or features such as color, size, shape context, atom type (in the case of a protein object) or so forth. An edge optionally may have attributes or features such as distance in the Euclidean space, or topological features such as an indicator feature (for example, having a value “1” if the edge is present between the pair of nodes in the graph and a value of “0” if the edge is not present) or a shortest-path distance feature (a measure of the shortest path along edges of the graph between the pair of nodes), a chemical bond type or strength (in the case of a protein object), or so forth. Still further, higher order attributes or features (for example, third order features) can also optionally be defined, such as angles between a set of three nodes (in which one of the three nodes is defined as the angle vertex) or shape of a triangle defined by a set of three nodes.
A graph embedded in Euclidean space and including suitable node, edge, or higher order attributes can provide a rich description of an object such as an image (or, an object within an image such as an image of a dog within a photograph) or the three-dimensional structure of a folded protein, or so forth. Graphs can thus be used in objects comparison, object retrieval, database indexing, or other applications. The comparison of graphs is known as graph matching, and is a type of pattern matching problem.
There are numerous graph similarity measures usable for graph matching, with a few representative measures outlined below. The following notation is used herein. A graph is represented by a set of node or vertices V and a set of edges E, that is, =(V,E). A node or vertex is denoted p, a pair of nodes or vertices is denoted (pi,pj) (where i,j are node index values), and the set of all possible pairs of nodes or vertices (pi,pj), regardless of whether there is an edge between them, is denoted V2. For the purpose of graph matching, the graph =(V,E) is matched with a graph =(V′,E′) by identifying a vertex mapping f:V→V′ that optimizes a match criterion denoted herein as g. In the examples herein, the match criterion g is a cost function that is to be minimized; however, a match criterion that is to be maximized is also contemplated.
Isometry is a graph similarity measure that considers the nodes without reference to the presence or absence of edges or the topology. The isometry cost function g is suitably written as:
                                                        g              isometric                        ⁡                          (                            )                                =                                                    arg                ⁢                                                                  ⁢                min                                            f                :                                  V                  →                                      V                    ′                                                                        ⁢                          {                                                ∑                                                            (                                                                        p                          1                                                ,                                                  p                          2                                                                    )                                        ⁢                    ε                    ⁢                                                                                  ⁢                                          V                      2                                                                                                                              ⁢                                                                                              d                      ⁡                                              (                                                                              p                            1                                                    ,                                                      p                            2                                                                          )                                                              -                                          d                      ⁡                                              (                                                                              f                            ⁡                                                          (                                                              p                                1                                                            )                                                                                ,                                                      f                            ⁡                                                          (                                                              p                                2                                                            )                                                                                                      )                                                                                                                          }                                      ,                            (        1        )            where f(pi) denotes the node or vertex to which the node or vertex pi maps in the graph =(V′,E′) using the mapping f:V→V′, and the function d( . . . ) denotes a distance measure in the Euclidean space. For an exact match, d(p1,p2)=d(f(p1), f(p2)) for every pair of nodes or vertices in V2. The isometry measure does not consider the node attributes or the presence or absence of edges, but rather searches for a set of nodes in =(V′,E′) that optimally match the locations of the nodes of the graph =(V,E).
Isomorphism and homeomorphism are graph similarity measures that include the isometry aspect and also incorporate similarity of the edges. For isomorphism, the cost function can be written as:
                                          g            isomorphic                    ⁡                      (                        )                          =                                            arg              ⁢                                                          ⁢              min                                      f              :                              V                →                                  V                  ′                                                              ⁢                                    {                                                                    ∑                                                                  (                                                                              p                            1                                                    ,                                                      p                            2                                                                          )                                            ⁢                      ε                      ⁢                                                                                          ⁢                                              V                        2                                                                                                                                            ⁢                                                                                                        d                        ⁡                                                  (                                                                                    p                              1                                                        ,                                                          p                              2                                                                                )                                                                    -                                              d                        ⁡                                                  (                                                                                    f                              ⁡                                                              (                                                                  p                                  1                                                                )                                                                                      ,                                                          f                              ⁡                                                              (                                                                  p                                  2                                                                )                                                                                                              )                                                                                                                                        +                                                      ∑                                                                  (                                                                              p                            1                                                    ,                                                      p                            2                                                                          )                                            ⁢                      ε                      ⁢                                                                                          ⁢                      E                                                                                                                      ⁢                                                                                1                      -                                                                        I                                                      E                            ′                                                                          ⁡                                                  [                                                      (                                                                                          f                                ⁡                                                                  (                                                                      p                                    1                                                                    )                                                                                            ,                                                              f                                ⁡                                                                  (                                                                      p                                    2                                                                    )                                                                                                                      )                                                    ]                                                                                                                                                    }                        .                                              (        2        )            The argument of the summation of the second term, namely |1−IE′(f(p1), f(p2))|, is derived from the expression |IE(p1,p2)−IE′(f)(p1), f(p2))| which has value “0” if there is an edge between (p1,p2) in  and between (f(p1), f(p2)) in . The simplification to |1−IE′(f(p1), f(p2))| results because the summation is only over those point pairs (p1,p2) in  that have edges (that is, IE(p1,p2)=1 for all (p1,p2)εE). Homeomorphism differs from isomorphism in that homeomorphism allows for intervening nodes in edges of the graph . This can be accounted for by modifying Equation (2) as follows:
                                          g            homeomorphic                    ⁡                      (                        )                          =                                            arg              ⁢                                                          ⁢              min                                      f              :                              V                →                                  V                  ′                                                              ⁢                                    {                                                                    ∑                                                                  (                                                                              p                            1                                                    ,                                                      p                            2                                                                          )                                            ⁢                      ε                      ⁢                                                                                          ⁢                                              V                        2                                                                                                                                            ⁢                                                                                                        d                        ⁡                                                  (                                                                                    p                              1                                                        ,                                                          p                              2                                                                                )                                                                    -                                              d                        ⁡                                                  (                                                                                    f                              ⁡                                                              (                                                                  p                                  1                                                                )                                                                                      ,                                                          f                              ⁡                                                              (                                                                  p                                  2                                                                )                                                                                                              )                                                                                                                                        +                                                      ∑                                                                  (                                                                              p                            1                                                    ,                                                      p                            2                                                                          )                                            ⁢                      ε                      ⁢                                                                                          ⁢                      E                                                                                                                      ⁢                                                                                                        d                        ⁡                                                  (                                                                                    p                              1                                                        ,                                                          p                              2                                                                                )                                                                    -                                                                        spd                                                      E                            ′                                                                          ⁡                                                  (                                                                                    f                              ⁡                                                              (                                                                  p                                  1                                                                )                                                                                      ,                                                          f                              ⁡                                                              (                                                                  p                                  2                                                                )                                                                                                              )                                                                                                                                                    }                        .                                              (        3        )            where d(p1,p2) is the length of the edge in Euclidean space between points (p1,p2)εE, and spdE′(f(p1), f(p2)) is the shortest path distance between points (f(p1), f(p2)) along paths in the set of paths E′ of the graph .
The various graph similarity measures have different utility for different applications. In general, one may expect isometric, isomorphic, and/or homeomorphic similarity measures to be useful in varying degrees for different object comparison problems. Moreover, none of Equations (1)-(3) take into account attributes of nodes, edges, or higher-order attributes. These may also be useful in varying degrees for different object comparison problems. In general, it is not apparent a priori which graph similarity measure or combination of measures is optimal for a given application.